#ifndef UNION_FIND_H
#define UNION_FIND_H
#include"QVector"

class union_find{
    static const int N = 2010 * 2;
    int fa[N];

    // 找x的祖先，并且把经过的点的father值也设置为x的祖先
    int find(int x) {
        if (x != fa[x]) {
            fa[x] = find(fa[x]);
        }
        return fa[x];
    }

    // a合并到b
    void join(int a, int b) {
        fa[find(a)] = find(b);
    }

public:
    bool possibleBipartition(int n, QVector<QVector<int>>& dislikes) {
        for (int i = 1; i <= n * 2; i++) {
            fa[i] = i;
        }
        for (int i = 0; i < dislikes.size(); i++) {
            int x = dislikes[i][0];
            int y = dislikes[i][1];
            join(x, y + n); // x和反y合并，表示x不能和y合并
            join(y, x + n); // y和反x合并，表示y不能和x合并
            if (find(x) == find(y)) {
                // 在之前合并操作之后，是否满足x,y不在同一个组
                return 0;
            }
        }
        return 1;
    }
};

#endif // UNION_FIND_H
